#ifndef RSIM_LIST_H
#define RSIM_LIST_H

/***************************************************************************
				List.h
                           -------------------
Copyright (c) 2009-2010 
Author: Kishor D. Bhalerao (kishor8dm@gmail.com)
Contributors: 

This file is associated with the Ph.D. dissertation,"ON METHODS FOR EFFICIENT
AND ACCURATE DESIGN AND SIMULATION OF MULTIBODY SYSTEMS", Bhalerao K.D,
Rensselaer Polytechnic Institute, 2010.

Redistribution and use in source and binary forms, with or without modification,
are permitted provided that the following conditions are met:

1.) Redistributions of source code must retain the above copyright notice, this
list of conditions and the following disclaimer.

2.) Redistributions in binary form must reproduce the above copyright notice,
this list of conditions and the following disclaimer in the documentation and/or
other materials provided with the distribution.

3.) The name of the authors, their employers, or sponsoring organizations may
not be used to endorse or promote products derived from this software without
specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
EVENT SHALL THE AUTHORS, THEIR EMPLOYERS, OR SPONSORING ORGANIZATIONS BE
LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
POSSIBILITY OF SUCH DAMAGE.
***************************************************************************/


#include <iostream>
#include <cstdlib>

////////////////////////////////////////////////////////////////////////
//	Implementation of a templatized linked list. The list is defined as 
//	List <T> L. The indexing is 0 based, that is the first object is
//	stored at location L(0). List creates its own copy. Modifying the
//	original would not modify the data stored in the List.
////////////////////////////////////////////////////////////////////////

namespace RSIM{

template <class T>
class Node{	
	public:
		T *data_;            // Each node has a data which is state.getQ()
		Node <T>* Parent_;   // The Parent_ is a pointer which points to the Parent of the current node 
		Node <T>* Child_;    // The Child_ is a pointer which points to the Child of the current node
		
		Node():data_(NULL),Parent_(NULL),Child_(NULL){}	// Once this class is created, all the pointers are null. 
		Node(const T &Var){data_ = new T; *data_=Var; Parent_=NULL; Child_=NULL;}
		//~Node(){if(data_!=NULL)delete data_;} // I commneted this
};

// All new data added at the end of the list
// This linked list to store the data to calculate the moving-window standard deviation and mean
template <class T>
class List{
	private:
		Node <T>* Root_; // The pointer Root_ points to the First object in the link
		Node <T>* Leaf_; // The pointer Leaf_ points to the Last object in the link
		int nNodes_;     // Shows the number of nodes
	public:
		// Constructor
		List():Root_(NULL),Leaf_(NULL),nNodes_(0){} // Once this class is created, all the pointers are null. 
		
		// Delete the space stored in List
		~List(){}; 

		// Add node at the end of the list (to current Leaf_ node)
		void addNode(const T& Var);
		
		// Add node at the beginning of the list (before current Root_ node)
		void prepend(const T&Var);
		
		// Deletes the root element. Length of the List decreased by 1
		void deleteRoot();
		
		// Delete the allocated space
		void clear();
		
		// Delete Node specified by NodeId
		// To be implemented.
		void deleteNode(const int& NodeId);		

		// Return total nodes
		int Length() const {return nNodes_;}
		int getnNodes() const {return nNodes_;}
		
		// Return Root
		const Node <T>* getRoot() const {return Root_;}		
		
		// Return  Leaf
		const Node <T>* getLeaf() const {return Leaf_;}
		
		int getLength() const {return nNodes_;}			
		
		// Print list information starting from specified node
		// A function void PrintInfo(void) must exist in the class 
		// T, which is called by this function for every node below
		// the Node Nd specified in the argument
		void PrintListInfo(const Node <T>* Nd);				
		
		// indexing starts from 0. 0th element is the Root. Returns a writable
		// reference to the data at specified index
		T& operator()(const int& index);
		T& operator[](const int& index);
		
		// Returns a constant reference to the data at specified index
		T& getNode(const int& index) const;
};

///////////////////////////////////////////////////////
//         List Functions
///////////////////////////////////////////////////////

template <class T>
void List<T>::addNode(const T& Var){
	nNodes_++;
	if (Root_==NULL){
		Root_ = new Node <T> (Var);
		Leaf_ = Root_;
	}
	else{
		Node <T>* tmp = Leaf_;
		Leaf_ = new Node <T> (Var);
		Leaf_->Parent_ = tmp;
		tmp->Child_ = Leaf_;
	}
}

///////////////////////////////////////////////////////

template <class T>
void List<T>::deleteRoot(){
	if(nNodes_==0){
		std::cout<<"\nList.h Nothing to delete";
	}
	else{
		Node <T>* tmp = Root_->Child_;		
		delete Root_;
		Root_ = tmp;			
		--nNodes_;
		
	}
}

///////////////////////////////////////////////////////

//template <class T>
//List<T>::~List(){
//	Node <T>* tmp = Root_;
//	for(int i=0;i<nNodes_;++i){		
//		//delete tmp;
//		tmp = tmp->Child_;		
//	}
//
//}

///////////////////////////////////////////////////////

// This function deletes all the nodes and sets the Root_ and Leaf_ as null
template <class T>
void List<T>::clear(){
	Node <T>* tmp = Root_;
	for(int i=0;i<nNodes_;++i){		
		//delete tmp;  // I commneted since it didnt work
		tmp = tmp->Child_;		
	}
	Root_ = NULL;
	Leaf_ = NULL;
	nNodes_ = 0;

}

///////////////////////////////////////////////////////

template <class T>
void List<T>::prepend(const T& Var){
	nNodes_++;
	if (Root_==NULL){
		Root_ = new Node <T> (Var);
		Leaf_ = Root_;
	}
	else{
		Node <T>* tmp = Root_;
		Root_ = new Node <T> (Var);
		Root_->Child_ = tmp;
		tmp->Parent_ = Root_;
	}
}

///////////////////////////////////////////////////////

template <class T>
T& List<T>::operator()(const int &index){
		Node <T>* tmp = Root_;
		for(int i=0;i<index;i++){
				tmp = tmp->Child_;
				if (tmp == NULL){
						std::cout<<"List.h: Index out of bounds. Exiting\n";
						exit(0);
				}
		}
		if(tmp==NULL){
				std::cout<<"List.h: List is empty. Exiting\n";
				exit(0);
		}
		return *((*tmp).data_);	
}

///////////////////////////////////////////////////////

template <class T>
T& List<T>::getNode(const int &index) const {
		Node <T>* tmp = Root_;
		for(int i=0;i<index;i++){
				tmp = tmp->Child_;
				if (tmp == NULL){
						std::cout<<"List.h: Index out of bounds. Exiting\n";
						exit(0);
				}
		}
		if(tmp==NULL){
				std::cout<<"List.h: List is empty. Exiting\n";
				exit(0);
		}
		return *((*tmp).data_);	
}

///////////////////////////////////////////////////////

template <class T>
T& List<T>::operator[](const int &index){
		Node <T>* tmp = Root_;
		for(int i=0;i<index;i++){
				tmp = tmp->Child_;
				if (tmp == NULL){
						std::cout<<"List.h: Index out of bounds. Exiting\n";
						exit(0);
				}
		}
		if(tmp==NULL){
				std::cout<<"List.h: List is empty, or attempt to access root. Exiting\n";
				exit(0);
		}
		return *((*tmp).data_);	
}

///////////////////////////////////////////////////////

template <class T>
void List<T>::PrintListInfo(const Node <T>* Nd){
		if(Nd != NULL){
				(Nd->data_)->PrintInfo();
				PrintListInfo(Nd->Child_);
		}
}

///////////////////////////////////////////////////////

} // namespace RSIM

#endif